package lanQiaoBei;
/*
*
* 利用位运算解决 面试题 异或 ^   N^N=0 N^0=N  N^NN=NN^N
* 1.给定一个数组：已知数组中只有一种数有奇数个 其他数字有偶数个 请以时间复杂度O（n） 空间复杂度O(1)找出那个奇数
* 2.给定一个数组：已知数组中只有两种数有奇数个 其他数字有偶数个 请以时间复杂度O（n） 空间复杂度O(1)找出那两个奇数
* */
public class PrintOddNum {
    public static void main(String[] args) {

    }
    public static void Second(int arr[]){
           int value=0;
           for(int i=0;i<arr.length;i++){
               value=value ^ arr[i];
           }
           //value=A^B 因为A!=B 所以 A与B的二进制位总至少有一位是不相同的
           //拿到从左往右第一个不同的位 即为1的位
          int value1=value &(~value+1);
           int value3=value;
           for(int i=0;i<arr.length;i++){
               if((arr[i] & value1)==1){
                   value=value1&arr[i];
               }
           }
        System.out.println(value+" "+(value3 ^ value));
    }
    public static void First(int arr[]){
           int value=0;
           for(int i=0;i<arr.length;i++){
               value=value ^ arr[i];//value 与arr[i] 异或
           }
           System.out.println(value);
    }
}
